/*
 * RELIC is an Efficient LIbrary for Cryptography
 * Copyright (C) 2007-2012 RELIC Authors
 *
 * This file is part of RELIC. RELIC is legal property of its developers,
 * whose names are not listed here. Please refer to the COPYRIGHT file
 * for contact information.
 *
 * RELIC is free software; you can redistribute it and/or
 * modify it under the terms of the GNU Lesser General Public
 * License as published by the Free Software Foundation; either
 * version 2.1 of the License, or (at your option) any later version.
 *
 * RELIC is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
 * Lesser General Public License for more details.
 *
 * You should have received a copy of the GNU Lesser General Public License
 * along with RELIC. If not, see <http://www.gnu.org/licenses/>.
 */

/**
 * @file
 *
 * Implementation of simultaneous point multiplication on binary elliptic
 * curves.
 *
 * @version $Id: relic_hb_mul_sim.c 1108 2012-03-11 21:45:01Z dfaranha $
 * @ingroup eb
 */

#include "string.h"

#include "relic_core.h"
#include "relic_hb.h"
#include "relic_util.h"

/*============================================================================*/
/* Private definitions                                                        */
/*============================================================================*/

#if HB_SIM == INTER || !defined(STRIP)

#if defined(HB_SUPER)

/**
 * Precomputes a table for a divisor class multiplication.
 *
 * @param[out] t				- the destination table.
 * @param[in] p					- the point to multiply.
 */
static void table_init(hb_t * t, hb_t p) {
	hb_set_infty(t[0]);
	hb_copy(t[1], p);
	hb_dbl(t[2], t[1]);
	hb_dbl(t[4], t[2]);
	hb_sub(t[3], t[4], p);
	hb_add(t[5], t[4], p);
	hb_dbl(t[6], t[3]);
	hb_add(t[7], t[6], p);
}

static void hb_mul_sim_imp(hb_t r, hb_t p, bn_t k, hb_t q, bn_t l, hb_t *t) {
	int len, l0, l1, i, n0, n1, gen;
	unsigned char win0[2 * FB_BITS + 1], win1[2 * FB_BITS + 1], *t0, *t1;
	hb_t table0[8];
	hb_t table1[8];

	for (i = 0; i < 8; i++) {
		hb_null(table0[i]);
		hb_null(table1[i]);
	}
	TRY {
		gen = (t == NULL ? 0 : 1);
		if (!gen) {
			for (i = 0; i < 8; i++) {
				hb_new(table0[i]);
			}
			table_init(table0, p);
			t = table0;
		}

		/* Prepare the precomputation table. */
		for (i = 0; i < 8; i++) {
			hb_new(table1[i]);
		}
		/* Compute the precomputation table. */
		table_init(table1, q);

		bn_rec_win(win0, &l0, k, 3);
		bn_rec_win(win1, &l1, l, 3);

		len = MAX(l0, l1);
		t0 = win0 + len - 1;
		t1 = win1 + len - 1;
		for (i = l0; i < len; i++) {
			win0[i] = 0;
		}
		for (i = l1; i < len; i++) {
			win1[i] = 0;
		}

		hb_set_infty(r);
		for (i = len - 1; i >= 0; i--, t0--, t1--) {
			hb_oct(r, r);

			n0 = *t0;
			n1 = *t1;
			if (n0 > 0) {
				hb_add(r, r, t[n0]);
			}
			if (n0 < 0) {
				hb_sub(r, r, t[-n0]);
			}
			if (n1 > 0) {
				hb_add(r, r, table1[n1]);
			}
			if (n1 < 0) {
				hb_sub(r, r, table1[-n1]);
			}
		}
		/* Convert r to affine coordinates. */
		hb_norm(r, r);
	}
	CATCH_ANY {
		THROW(ERR_CAUGHT);
	}
	FINALLY {
		/* Free the precomputation tables. */
		if (!gen) {
			for (i = 0; i < 8; i++) {
				hb_free(table0[i]);
			}
		}
		for (i = 0; i < 8; i++) {
			hb_free(table1[i]);
		}
	}
}
#endif /* HB_ORDIN || HB_SUPER */

#endif /* HB_SIM == INTER */

/*============================================================================*/
	/* Public definitions                                                         */
/*============================================================================*/

#if HB_SIM == BASIC || !defined(STRIP)

void hb_mul_sim_basic(hb_t r, hb_t p, bn_t k, hb_t q, bn_t l) {
	hb_t t;

	hb_null(t);

	TRY {
		hb_new(t);
		hb_mul(t, q, l);
		hb_mul(r, p, k);
		hb_add(t, t, r);
		hb_norm(r, t);

	} CATCH_ANY {
		THROW(ERR_CAUGHT);
	}
	FINALLY {
		hb_free(t);
	}
}

#endif

#if HB_SIM == TRICK || !defined(STRIP)

void hb_mul_sim_trick(hb_t r, hb_t p, bn_t k, hb_t q, bn_t l) {
	hb_t t0[1 << (HB_WIDTH / 2)];
	hb_t t1[1 << (HB_WIDTH / 2)];
	hb_t t[1 << HB_WIDTH];
	bn_t n;
	int d, l0, l1, w;
	unsigned char w0[2 * FB_BITS + 1], w1[2 * FB_BITS + 1];

	bn_null(n);

	for (int i = 0; i < 1 << HB_WIDTH; i++) {
		hb_null(t[i]);
	}

	for (int i = 0; i < 1 << (HB_WIDTH / 2); i++) {
		hb_null(t0[i]);
		hb_null(t1[i]);
	}

	w = HB_WIDTH / 2;

	TRY {
		bn_new(n);

		hb_curve_get_ord(n);
		d = bn_bits(n);
		d = ((d % w) == 0 ? (d / w) : (d / w) + 1);

		for (int i = 0; i < (1 << w); i++) {
			hb_new(t0[i]);
			hb_new(t1[i]);
		}
		for (int i = 0; i < (1 << HB_WIDTH); i++) {
			hb_new(t[i]);
		}

		hb_set_infty(t0[0]);
		for (int i = 1; i < (1 << w); i++) {
			hb_add(t0[i], t0[i - 1], p);
		}

		hb_set_infty(t1[0]);
		for (int i = 1; i < (1 << w); i++) {
			hb_add(t1[i], t1[i - 1], q);
		}

		for (int i = 0; i < (1 << w); i++) {
			for (int j = 0; j < (1 << w); j++) {
				hb_add(t[(i << w) + j], t0[i], t1[j]);
			}
		}

		bn_rec_win(w0, &l0, k, w);
		bn_rec_win(w1, &l1, l, w);

		for (int i = l0; i < l1; i++) {
			w0[i] = 0;
		}
		for (int i = l1; i < l0; i++) {
			w1[i] = 0;
		}

		hb_set_infty(r);
		for (int i = MAX(l0, l1) - 1; i >= 0; i--) {
			for (int j = 0; j < w; j++) {
				hb_dbl(r, r);
			}
			hb_add(r, r, t[(w0[i] << w) + w1[i]]);
		}
		hb_norm(r, r);
	} CATCH_ANY {
		THROW(ERR_CAUGHT);
	}
	FINALLY {
		bn_free(n);
		for (int i = 0; i < (1 << w); i++) {
			hb_free(t0[i]);
			hb_free(t1[i]);
		}
		for (int i = 0; i < (1 << HB_WIDTH); i++) {
			hb_free(t[i]);
		}
	}
}
#endif

#if HB_SIM == INTER || !defined(STRIP)

void hb_mul_sim_inter(hb_t r, hb_t p, bn_t k, hb_t q, bn_t l) {
	hb_mul_sim_imp(r, p, k, q, l, 0);
}

#endif

#if HB_SIM == JOINT || !defined(STRIP)

void hb_mul_sim_joint(hb_t r, hb_t p, bn_t k, hb_t q, bn_t l) {
	hb_t t[5];
	int u_i, len, offset;
	signed char jsf[4 * (FB_BITS + 1)];
	int i;

	hb_null(t[0]);
	hb_null(t[1]);
	hb_null(t[2]);
	hb_null(t[3]);
	hb_null(t[4]);

	TRY {
		for (i = 0; i < 5; i++) {
			hb_new(t[i]);
		}

		hb_set_infty(t[0]);
		hb_copy(t[1], q);
		hb_copy(t[2], p);
		hb_add(t[3], p, q);
		hb_sub(t[4], p, q);

		bn_rec_jsf(jsf, &len, k, l);

		hb_set_infty(r);

		i = bn_bits(k);
		offset = MAX(i, bn_bits(l)) + 1;
		for (i = len - 1; i >= 0; i--) {
			hb_dbl(r, r);
			if (jsf[i] != 0 && jsf[i] == -jsf[i + offset]) {
				u_i = jsf[i] * 2 + jsf[i + offset];
				if (u_i < 0) {
					hb_sub(r, r, t[4]);
				} else {
					hb_add(r, r, t[4]);
				}
			} else {
				u_i = jsf[i] * 2 + jsf[i + offset];
				if (u_i < 0) {
					hb_sub(r, r, t[-u_i]);
				} else {
					hb_add(r, r, t[u_i]);
				}
			}
		}
		hb_norm(r, r);
	}
	CATCH_ANY {
		THROW(ERR_CAUGHT);
	}
	FINALLY {
		for (i = 0; i < 5; i++) {
			hb_free(t[i]);
		}
	}
}

#endif

void hb_mul_sim_gen(hb_t r, bn_t k, hb_t q, bn_t l) {
	hb_t gen;

	hb_null(gen);

	TRY {
		hb_new(gen);

		hb_curve_get_gen(gen);

#if HB_FIX == OCTUP && defined(HB_PRECO)
		hb_mul_sim_imp(r, gen, k, q, l, hb_curve_get_tab());
#else
		hb_mul_sim(r, gen, k, q, l);
#endif
	}
	CATCH_ANY {
		THROW(ERR_CAUGHT);
	}
	FINALLY {
		hb_free(gen);
	}
}
